import java.util.ArrayList;
import java.util.List;

/**
 * 面试题57-2：和为s的连续正数序列
 */
public class Offer_57_II {
    /**
     * 双指针
     * <p>
     * 时间复杂度：O(target)
     * <p>
     * 空间复杂度：O(1)
     */
    public int[][] findContinuousSequence(int target) {
        // 至少含有两个数的连续正整数序列
        int left = 1, right = 2;
        // 序列和
        int sum = left + right;
        // 存放结果
        List<int[]> list = new ArrayList<>();

        while (left <= target / 2 && left < right) {
            if (sum < target) {
                // 序列和小于目标值
                right++;
                sum += right;
            } else if (sum > target) {
                // 序列和大于目标值
                sum -= left;
                left++;
            } else {
                // 序列和等于目标值
                int[] arr = new int[right - left + 1];
                for (int i = left; i <= right; i++) {
                    arr[i - left] = i;
                }
                list.add(arr);
                // 以 left 为起点的合法解最多只有一个，所以需要枚举下一个起点
                sum -= left;
                left++;
            }
        }
        return list.toArray(new int[list.size()][]);
    }
}
